import collections


class Solution(object):
    def boldWords(self, words, s):
        """
        :type words: List[str]
        :type s: str
        :rtype: str
        """
        n = len(s)
        out = collections.deque()
        for i in range(n):
            for word in words:
                if i + len(word) <= n and s[i: i + len(word)] == word:
                    out.append([i, i + len(word) - 1])
        stack = collections.deque()
        if not out:
            return s
        else:
            stack.append(out[0])
            for i in range(1, len(out)):
                if out[i][0] <= stack[-1][1] + 1:
                    node = stack.pop()
                    stack.append([node[0], max(node[1], out[i][1])])
                else:
                    stack.append(out[i])
        out_s = ''
        for i in range(len(stack)):
            if i == 0:
                out_s += s[: stack[0][0]]
                out_s += ('<b>' + s[stack[0][0]: stack[0][1] + 1] + '</b>')
            else:
                out_s += s[stack[i - 1][1] + 1: stack[i][0]]
                out_s += ('<b>' + s[stack[i][0]: stack[i][1] + 1] + '</b>')
        out_s += s[stack[-1][1] + 1:]
        return out_s


data = Solution()
# words = ["ab", "bc"]
# s = "aabcd"
# print(data.boldWords(words, s))
# words = ["ab", "cb"]
# s = "aabcd"
# print(data.boldWords(words, s))
# words = ["abcd"]
# s = "ab"
# print(data.boldWords(words, s))
# words = ["ccb","b","d","cba","dc"]
# s = "eeaadadadc"
# print(data.boldWords(words, s))
words = ["b", "dee", "a", "ee", "c"]
s = "cebcecceab"
print(data.boldWords(words, s))
